/*
https://leetcode-cn.com/problems/find-majority-element-lcci/solution/zhu-yao-yuan-su-by-leetcode-solution-xr1p/
 */
public class SolutionInterview17_10 {
    public int majorityElement(int[] nums) {
        int a=-1,acount=0;
        for (int num : nums) {
            if (acount==0){
                acount++;
                a=num;
            }else if (a==num){
                acount++;
            }else {
                acount--;
            }
        }
        if (acount==0){
            return -1;
        }
        int count=0;
        for (int num : nums) {
            if (num==a){
                count++;
            }
        }
        if (count>nums.length/2){
            return a;
        }else{
            return -1;
        }
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview17_10().majorityElement(new int[]{1,2,5,9,5,9,5,5,5}));
    }
}
